/// @tags: Mobius inversion
#include <algorithm>
#include <cctype>
#include <cstdio>

typedef long long ll;

int const N = 5e6 + 5, mod = 1e9 + 7;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

int n, m, k, T, cnt;
int pri[N / 10], g[N], priexp[N / 10];
bool vis[N];

ll qpow(ll base, int index) {
  ll res = 1;
  while (index) {
    if (index & 1) res = res * base % mod;
    base = base * base % mod;
    index >>= 1;
  }
  return res;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4449 于神之怒加强版.in", "r", stdin);
  freopen("P4449 于神之怒加强版.out", "w", stdout);
#endif
#endif

  read(T), read(k);
  g[1] = 1;
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) {
      pri[++cnt] = i;
      priexp[cnt] = qpow(i, k);
      g[i] = priexp[cnt] - 1;
      if (g[i] < 0) g[i] += mod;
    }
    for (int j = 1; j <= cnt && pri[j] * i < N; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) {
        g[i * pri[j]] = 1ll * g[i] * priexp[j] % mod;
        break;
      }
      g[i * pri[j]] = 1ll * g[i] * g[pri[j]] % mod;
    }
  }
  for (int i = 1; i < N; ++i)
    if ((g[i] += g[i - 1]) >= mod) g[i] -= mod;
  while (T--) {
    read(n), read(m);
    if (n > m) std::swap(n, m);
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
      r = std::min(n / (n / l), m / (m / l));
      if ((ans += 1ll * (g[r] - g[l - 1] < 0 ? g[r] - g[l - 1] + mod : g[r] - g[l - 1]) *
                  (n / r) % mod * (m / r) % mod) >= mod)
        ans -= mod;
    }
    printf("%d\n", ans);
  }
  return 0;
}